Floyd(Graph &G, DIst **&D) {
    int i, j, v;
    D = new Dist *[G.VerticesNum()];
    for (i = 0; i < G.VerticesNUm(); i++)
        D[i] = new Dist[G.VerticesNum()];
    for (i = 0; i < G.VerticesNum(); i++) {
        for (j = 0; j < G.VerticesNum(); j++) {
            if (i == j) {
                D[i][j].length = 0;
                D[i][j].pre = i;
            } else {
                D[i][j].length = INFINITE;
                D[i][j].pre = -1;
            }
        }
        for (v = 0; v < G.VerticesNum(); v++) {
            for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) {
                D[v][G.ToVertex(e)].length = G.Weight(e);
                D[v][G.ToVertex(e)].pre = v;
            }
        }
        // 加入新节点后，更新那些边短的路径长度
        for (v = 0; v < G.VerticesNum(); v++)
            for (i = 0; i < G.VerticesNum(); i++)
                for (j = 0; j < G.VerticesNum(); j++)
        if(D[i][j].length>(D[i][v].length+D[v][j].length)
	{
                        D[i][j].length = D[i][v].length + D[v][j].length;
                        D[i][j].pre = D[v][j].pre;
	}
    }
}
